package leetcode_181_200;

public class maxProfit_188 {
    public int maxProfit(int k, int[] prices) {
        //3,   2  ,  6  ,  5  ,   0  ,  3
        int n = prices.length;
        int[] buys = new int[k + 1];   //buy[i] 表示第i次买入的最大收益
        int[] sells = new int[k + 1];    //sell[i] 表示第i次卖出的最大收益
        for (int i = 0; i <= k; i++)
            buys[i] = Integer.MIN_VALUE;//每次买入时，都使处于买过股票的状态
        sells[0] = 0;
        for (int price : prices) {                                     //需要注意遍历的是第i次买入或者卖出发生在每一天的情况
            // 获取今天是第几次交易时，的利润最大
            for (int i = 1; i < k + 1; i++) {
                //买的第 i 个股票
                //该股票要么来自之前已经持有，buy[i]不变
                // 要么是今天买入，用上次的钱进行交易 sells[i - 1] - price
                // 比较利润
                buys[i] = Math.max(buys[i], sells[i - 1] - price);
                //卖的第 i 个股票，
                // 之前卖的   不处理 仍为sells[i]
                // 今天卖的   buys[i] + price
                sells[i] = Math.max(sells[i], buys[i] + price);
            }
        }
        return sells[k];
    }
}
